package com.cty._01_Base._03_02_DuplicationInArrayNoEdit;

/**
 * @Auther: cty
 * @Date: 2020/6/25 10:49
 * @Description: 面试题3：数组中重复的数字
 * 题目二：不修改数组找出重复的数字
 *      在一个长度为n+1的数组里所有的数字都在1~n的范围内，所以数组中至少有一个数字是重复的。
 *      请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组
 *      {2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或3。
 * @version: 1.0
 */
public class DuplicationInArrayNoEdit {
    /**
     * 不修改数组找出重复的数字（空间优先）
     * 要求：
     *      不可以修改数组
     *      找出数组中任意一个重复的数组
     * 效率：
     *      时间  O(N*logN)
     *      空间  O(1)
     * @param array
     * @param length
     * @return
     */
    public static int getDuplicate(int[] array, int length){
        if(array==null || length==0)
            return -1;  // 数组为空指针或长度为0

        for(int i=0; i<length; i++)
            if(array[i]<1 || array[i]>length)
                return -2;  // 数组中包含不在1~n范围内的数字

        int start = 1;
        int end = length-1;
        while(end >= start){
            int median = (end + start)>>1;
            int scopeOfStart2Median = median - start + 1;
            int numOfStart2Median = getNumOfStart2End(array, length, start, median);

            if(start == end)
                if(numOfStart2Median > 1)
                    return start;
                else
                    break;

            if(numOfStart2Median > scopeOfStart2Median)
                end = median;
            else
                start = median + 1;
        }  // end while
        return -3;  // 数组中不包含重复的数字
    }  // end getDuplicate()

    /**
     * 统计数组中数字大小在[start,end]范围内的个数
     * @param array
     * @param length
     * @param start
     * @param end
     * @return
     */
    public static int getNumOfStart2End(int[] array, int length, int start, int end){
        int count = 0;
        for(int i=0; i<length; i++)
            if(array[i]>=start && array[i]<=end)
                count++;
        return count;
    }  // end getNumOfStart2End()


    /**
     * 不修改数组找出重复的数字（时间优先）
     * 要求：
     *      不可以修改数组
     *      找出数组中任意一个重复的数组
     * 效率：
     *      时间  O(N)
     *      空间  O(N)
     * @param array
     * @param length
     * @return
     */
    public static int getDuplicate02(int[] array, int length){
        if(array==null || length==0)
            return -1;  // 数组为空或长度为0

        for(int i=0; i<length; i++)
            if(array[i]<1 || array[i]>length)
                return -2;  // 数组中包含不在1~n范围内的数字

        int[] temp = new int[length];
        for(int i=0; i<length; i++)
            if(temp[array[i]] != array[i])
                temp[array[i]] = array[i];
            else
                return array[i];
        return -3;  // 数组中不包含重复的数字
    }  // end getDuplicate02()

}  // end class
